package com.hanxiaozhang.graph;

import java.util.*;

/**
 * 〈一句话功能简述〉<br>
 * 〈拓扑排序〉
 *
 * @author hanxinghua
 * @create 2021/9/26
 * @since 1.0.0
 */
public class TopologySort {


    /**
     * 拓扑排序
     *
     * 图，但是不能出现循环
     * @param graph
     * @return
     */
    public static List<Node> topologySorted(Graph graph) {
        // key --> 某一个node  value --> 剩余的入度
        HashMap<Node, Integer> inMap = new HashMap<>(16);
        // 入度为0的点，才能进这个队列
        Queue<Node> zeroInQueue = new LinkedList<>();
        // 初始化inMap，并将入度为0点，放入zeroInQueue
        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0) {
                zeroInQueue.add(node);
            }
        }
        // 拓扑排序的结果，依次加入result
        List<Node> result = new ArrayList<>();
        // zeroInQueue不为空循环
        while (!zeroInQueue.isEmpty()) {
            Node cur = zeroInQueue.poll();
            result.add(cur);
            // 消除邻接节点的入度
            for (Node next : cur.nexts) {
                inMap.put(next, inMap.get(next) - 1);
                if (inMap.get(next) == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}
